#include <stdio.h>
#include <stdlib.h>

// 二叉搜索树的节点结构
typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
} Node;

// 创建一个新节点
Node* createNode(int key) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        return NULL;
    }
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 插入一个新节点
Node* insert(Node *root, int key) {
    if (root == NULL) {
        return createNode(key);
    }

    if (key < root->key) {
        root->left = insert(root->left, key);  // 插入到左子树
    } else if (key > root->key) {
        root->right = insert(root->right, key); // 插入到右子树
    }
    // 如果key == root->key，则不做插入，树中已有相同的键值

    return root;
}

// 查找一个节点
Node* search(Node *root, int key) {
    if (root == NULL || root->key == key) {
        return root;
    }

    if (key < root->key) {
        return search(root->left, key); // 在左子树中查找
    } else {
        return search(root->right, key); // 在右子树中查找
    }
}

// 查找最小值节点
Node* findMin(Node *root) {
    while (root && root->left) {
        root = root->left;
    }
    return root;
}

// 删除一个节点
Node* delete(Node *root, int key) {
    if (root == NULL) {
        return root; // 树为空时返回NULL
    }

    if (key < root->key) {
        root->left = delete(root->left, key); // 在左子树中删除
    } else if (key > root->key) {
        root->right = delete(root->right, key); // 在右子树中删除
    } else {
        // 找到要删除的节点
        if (root->left == NULL) {
            Node *temp = root->right;
            free(root);  // 删除当前节点
            return temp; // 返回右子树的节点
        } else if (root->right == NULL) {
            Node *temp = root->left;
            free(root);  // 删除当前节点
            return temp; // 返回左子树的节点
        } else {
            // 有两个子节点的情况
            Node *temp = findMin(root->right); // 找到右子树中的最小节点
            root->key = temp->key; // 用最小节点的值替换当前节点的值
            root->right = delete(root->right, temp->key); // 删除右子树中的最小节点
        }
    }

    return root;
}

// 中序遍历（递归）
void inorder(Node *root) {
    if (root != NULL) {
        inorder(root->left);  // 先遍历左子树
        printf("%d ", root->key);  // 打印当前节点的键
        inorder(root->right); // 再遍历右子树
    }
}

// 主函数
int main() {
    Node *root = NULL;

    // 插入一些节点
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Inorder traversal: ");
    inorder(root);  // 打印中序遍历结果
    printf("\n");

    // 查找节点
    int key = 40;
    Node *foundNode = search(root, key);
    if (foundNode) {
        printf("Found node with key %d\n", key);
    } else {
        printf("Node with key %d not found\n", key);
    }

    // 删除节点
    root = delete(root, 50);
    printf("Inorder traversal after deletion of 50: ");
    inorder(root);  // 删除节点后再打印中序遍历结果
    printf("\n");

    return 0;
}
